The present invention relates to the field of cryptography in general and more particularly to public key cryptosystems.
In some conventional public key cryptosystems, two keys may be generated by both a sender and a recipient who wish to communicate securely with each other. In particular, the sender and the recipient may generate a public key that may be known to others and a private key which only the creator may know. For example, in a Revest Shamir Adleman (RSA) cryptosystem each user""s public key may be publicly known while each user""s private key may be known only to the respective user. To send a secure communication, the sender encrypts a message using the recipient""s public key. The recipient decrypts the message using the recipient""s private key. Similarly, the roles may be reversed wherein the original recipient may wish to respond to the original sender""s message. Accordingly, the original recipient encrypts the response using the original sender""s public key and the original sender may decrypt the response using the original sender""s private key.
It is known to generate the public and private keys used in a public key cryptosystem based on two large prime numbers. For example, the public key may be generated by multiplying two prime numbers while the private key may be generated by applying modular operations to the public key which may cause the public and private keys to be large (i.e., a large number of bits). For example, the two prime numbers described above may include one hundred bits each. Consequently, the encryption and decryption of messages may involve operations with large numbers which may be time consuming without using a dedicated processor and large registers to store intermediate results during the encryption and decryption process. Unfortunately, a dedicated processor and large registers may occupy relatively large portions of a circuit board and be economically unfeasible. In view of the above, the is a need to improve public key cryptosystems that use large numbers to perform encryption and decryption.
It is, therefore, an object of the present invention to provide for improvement in the encryption and decryption of communications in public key cryptosystems.
It is another object of the present invention to allow a reduction in the size of registers used to carry out modular operations used in encryption and decryption of communications in public key cryptosystems.
It is a further object of the present invention to allow a reduction in the interconnect used to carry out modular operations used in encryption and decryption of communications in public key cryptosystems.
In still another aspect of the present invention, the first and second data are accessed in an external memory device. The external memory device may comprise a dual port synchronous RAM. Using an external memory device may reduce the need to provide large size registers. For example, a portion of the external memory device may be allocated for storage of intermediate results thereby reducing the need to provide dedicated registers on an integrated circuit board which carries the circuitry used to implement the public key cryptosystem according to the present invention.